package com.example.demo.suanfa_2tree;

import java.util.Stack;

/**
 * 适用非递归方式，实现二叉树的分递归，前序，后序，中序遍历
 */
public class UnRecursiveTraversalBTDemo {


    static class Node {
        int value;
        Node left;
        Node right;
    }


    public void pre(Node node) {
        if (node == null) {
            return;
        }
        Stack<Node> stack = new Stack<>();
        stack.add(node);
        System.out.println("tree pre sort");
        while (!stack.isEmpty()) {
            Node pop = stack.pop();
            System.out.println(pop);

            if (pop.right != null) {
                stack.add(pop.right);
            }

            if (pop.left != null) {
                stack.add(node.left);
            }
        }
    }

    public void post(Node node) {
        if (node == null) {
            return;
        }
        Stack<Node> stack = new Stack<>();
        stack.add(node);
        System.out.println("tree pre sort");
        Stack<Node> postStack = new Stack<>();
        while (!stack.isEmpty()) {
            Node pop = stack.pop();
            postStack.add(pop);
            // 与先序不同！！！
            if (pop.left != null) {
                stack.add(node.left);
            }
            if (pop.right != null) {
                stack.add(pop.right);
            }
        }
        while (!postStack.isEmpty()) {
            System.out.println(postStack.pop());
        }
    }

    // 感觉这块是个错误代码呢

    /**
     * 将当前节点 的左树全部压入栈中
     * @param node
     * @param stack
     */
    public void leftIn(Node node,Stack<Node> stack){
        if (node != null){
            stack.push(node);
            while (node.left!=null){
                stack.push(node.left);
                node = node.left;
            }
        }
    }

    public void mid(Node node){
        if (node!=null){
            Stack<Node> stack = new Stack<>();
            leftIn(node, stack);
           while (!stack.isEmpty()) {
               Node pop = stack.pop();
               System.out.println(pop);
               if (pop.right != null) {
                   leftIn(pop.right, stack);
               }
           }
        }
    }

    /**
     * 中序
     * @param node
     */
    public void in(Node cur){
        if (cur!=null){
            Stack<Node> stack = new Stack<>();
            stack.push(cur);
            stack.add(cur);// ?
            while (!stack.isEmpty()){
                if (cur.left!=null){
                    stack.push(cur);
                    cur = cur.left;
                }else {
                    Node pop = stack.pop();
                    cur = pop.right;
                    System.out.println(pop.value);
                }
            }
        }
    }
}
